package com.gwcloud.leetcode.offers;

import java.util.Arrays;

/** 
* @ClassName   : Leetcode0450 
* @author      : ganwei 
* @date        : 2020年6月6日 
* @Description : TODO 
*/
public class Leetcode0450 {
	String result = "";
	/**
	 * -数组按字符排序
	 */
    public String minNumber(int[] nums) {
    	
    	//backtrace(nums, 0, new StringBuilder(), new boolean[nums.length]);
    	//return result;
    	
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++) 
            strs[i] = String.valueOf(nums[i]);
        Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
        StringBuilder res = new StringBuilder();
        for(String s : strs)
            res.append(s);
        
        return res.toString();

    }
    /**
     * -回溯主体,超时，不行
     */
    public void backtrace(int[] nums, int curlen, StringBuilder sb, boolean[] visited) {
    	if(curlen == nums.length) {
    		if(result.equals("")) {
    			result = sb.toString();
    		}
    		if(sb.toString().compareTo(result) < 0) {
    			result = sb.toString();
    		}
    	}
    	
    	for(int i = 0; i < nums.length; i++) {
    		if(visited[i]) {
    			continue;
    		}
    		String numi = String.valueOf(nums[i]);
    		visited[i] = true;
    		sb.append(numi);
    		
    		backtrace(nums, curlen+1, sb, visited);
    		
    		visited[i] = false;
    		sb = sb.delete(sb.length()-numi.length(),sb.length());
    				
    	}
    }
    
}
